/**
 * list.h
 * 链表类型及操作声明
 * 
 * 若希望节省内存可使用基于 struct list_node  的单链表
 * 若希望操作更多可使用基于 struct listd_node 的双链表
 * 对于哈希表，基于单链表或双链表结点均能实现
 *
 * 结合 struct listh_head struct listh_node 
 * 实现哈希表像是二者的一种折中
 *
 * 双链表和哈希链表在 linux 内核中皆有实现
 *
 * 竹影半墙
 * 2023.09
 */
#ifndef LIST_H
#define LIST_H

#include "base.h"

struct list_node {
    struct list_node *next;
};

/**
 * 初始化结点 @n
 */
static inline void list_init(struct list_node *n)
{
    n->next = NULL;
    return ;
}

/**
 * 根据结点 @h 判断单链表是否为空
 */
static inline bool list_empty(struct list_node *h)
{
    return !h->next;
}

/**
 * 在相应单链表中于结点 @p 后新增结点 @n
 */
static inline void 
list_add(struct list_node *n, struct list_node *p)
{
    n->next = p->next;
    p->next = n;
    return ;
}
/**
 * 在数据对象 @prev 后新增数据对象 @cheif
 * @mbr 为数据对象用于串联单链表的结点命名
 */
#define list_chief_add(chief, prev, mbr) \
    list_add(&(chief)->mbr, &(prev)->mbr)

/**
 * 在相应单链表中删除结点 @p 之后的结点 @n
 */
static inline void 
list_del(struct list_node *n, void *prev)
{
    struct list_node *p = (struct list_node*)prev;

    p->next = n->next;
    return ;
}
/**
 * 删除数据对象 @prev 后的数据对象 @cheif
 * @mbr 为数据对象用于串联单链表的结点命名
 */
#define list_chief_del(chief, prev, mbr) \
    list_del(&(chief)->mbr, prev)

/**
 * 将单链表头结点 @s 后续结点移动到空头结点 @d 上
 */
static inline void 
list_move(struct list_node *d, struct list_node *s)
{
    d->next = s->next;
    s->next = NULL;
    return ;
}

/**
 * 将相应单链表结点 @n 后续结点切断加到空头结点 @d 上
 */
static inline void 
list_cut(struct list_node *d, struct list_node *n)
{
    d->next = n->next;
    n->next = NULL;
    return ;
}

/**
 * 单链表结点遍历
 * @node 所遍历结点地址
 * @head 头结点地址
 */
#define list_foreach(node, head)                        \
    for (node=(head)->next; node ; node=node->next)

/**
 * 单链表结点遍历，支持 list_add/list_del(node)
 * @prev @node 前向结点地址
 * @node 存结点地址
 * @head 头结点地址
 */
#define list_foreach_safe(node, prev, head)             \
    for (prev=head, node=(head)->next;                  \
         node;                                          \
         prev=(prev->next==node) ? node : prev,         \
         node=(prev->next==node) ? node->next : prev->next)

/**
 * 单链表数据对象地址获取
 * @node  结点地址
 * @cheif 数据对象指针类型变量
 * @mbr   数据对象用于串联单链表的结点命名
 */
#define list_chief(node, chief, mbr) ({                 \
    (node)                               ?              \
    startof(node, typeof(*(chief)), mbr) :              \
    (NULL);                                             \
})

/**
 * 单链表数据对象遍历
 * @chief 所遍历数据对象地址
 * @head  头结点地址
 * @mbr   数据对象用于串联单链表的结点命名
 */
#define list_foreach_chief(chief, head, mbr)            \
    for (chief = list_chief((head)->next,chief,mbr);    \
         chief;                                         \
         chief = list_chief(chief->mbr.next,chief,mbr))

#define list_node_to_chief(chief, node)                 \
    ({ (typeof(chief)) (node); })

#define list_chief_to_node_next(chief)                  \
    ({ ((struct list_node*)(chief))->next; })
/**
 * 单链表数据对象遍历，支持 list_cheif_add/list_chief_del 
 * @chief 所遍历数据对象地址
 * @prev  实际值为 @chief 前向结点地址
 * @head  头结点地址
 * @mbr   数据对象用于串联单链表的结点命名
 */
#define list_foreach_chief_safe(chief, prev, head, mbr) \
    for (prev  = list_node_to_chief(chief, head),       \
         chief = list_chief((head)->next, chief, mbr);  \
                                                        \
         chief;                                         \
                                                        \
         prev  =                                        \
         list_chief_to_node_next(prev) == &chief->mbr ? \
         list_node_to_chief(chief, &chief->mbr) : prev, \
         chief = list_chief(list_chief_to_node_next(prev), chief, mbr))

#if 0
#endif
struct listd_node {
    struct listd_node *next;
    struct listd_node *prev;
};

/**
 * 初始化结点 @n
 */
static inline void listd_init(struct listd_node *n)
{
    n->prev = n->next = n;
    return ;
}

/**
 * 根据结点 @h 判断双链表是否为空
 */
static inline bool listd_empty(struct listd_node *h)
{
    return h->next == h;
}

static inline void 
listd_add(struct listd_node *n,
    struct listd_node *prev, struct listd_node *next)
{
    next->prev = n;
    prev->next = n;
    n->next = next;
    n->prev = prev;
    return ;
}

/**
 * 在相应双链表头部新增结点
 * 将结点 @n 新增到头结点 @h 之后
 */
static inline void 
listd_add_head(struct listd_node *n, struct listd_node *h)
{
    listd_add(n, h, h->next);
    return ;
}

/**
 * 在相应双链表尾部新增结点
 * 将结点 @n 新增到头结点 @h 之前
 */
static inline void 
listd_add_tail(struct listd_node *n, struct listd_node *h)
{
    listd_add(n, h->prev, h);
    return ;
}

/**
 * 将结点 @n 从相应双链表中删除
 */
static inline void 
listd_del(struct listd_node *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    return ;
}
/**
 * 将数据对象 @chief 从相应双链表中删除
 * @mbr 为数据对象用于串联双链表的结点命名
 */
#define listd_chief_del(chief, mbr) listd_del(&(chief)->mbr)

/**
 * 根据链表头 @h 将相应双链表循环左移一次
 */
static inline void 
listd_shift_left(struct listd_node *h)
{
    struct listd_node *n;

    if (unlikely(listd_empty(h)))
        return ;
    n = h->next;
    listd_del(n);
    listd_add_tail(n, h);
    return ;
}

/**
 * 在相应双链表中
 * 将头结点 @s 之后的结点移动到头结点 @d 之后
 */
static inline void 
listd_move_head(struct listd_node *d, struct listd_node *s)
{
    if (unlikely(listd_empty(s)))
        return ;
    s->prev->next = d->next;
    d->next->prev = s->prev;

    s->next->prev = d;
    d->next = s->next;
    if (d->prev == d)
        d->prev = s->prev;
    return ;
}

/**
 * 在相应双链表中
 * 将头结点 @s 之后的结点移动到头结点 @d 之前
 */
static inline void 
listd_move_tail(struct listd_node *d, struct listd_node *s)
{
    if (unlikely(listd_empty(s)))
        return ;
    s->next->prev = d->prev;
    d->prev->next = s->next;

    s->prev->next = d;
    d->prev = s->prev;
    return ;
}

/**
 * 在相应双链表中
 * 将头结点 @h 之后结点从结点 @n 处切断
 * 并将结点 @n 及后续结点附在空头结点 @t 上
 */
static inline void 
listd_cut(struct listd_node *t, struct listd_node *n,
    struct listd_node *h)
{
    struct listd_node *last = h->prev;

    h->prev = n->prev;
    n->prev->next = h;

    t->next = n;
    t->prev = last;
    n->prev = t;
    last->next = t;
    return ;
}

/**
 * 在相应双链表中
 * 将头结点 @s 之后结点从结点 @n 处切断
 * 并将切断结点加到头结点 @d 之后
 */
static inline void 
listd_cut_head(struct listd_node *n,
    struct listd_node *d, struct listd_node *s)
{
    struct listd_node t;

    if (unlikely(listd_empty(s)))
        return ;
    listd_init(&t);
    listd_cut(&t, n, s);
    listd_move_head(d, &t);
    return ;
}

/**
 * 在相应双链表中
 * 将头结点 @s 之后结点从结点 @n 处切断
 * 并将切断结点加到头结点 @d 之前
 */
static inline void 
listd_cut_tail(struct listd_node *n, 
    struct listd_node *d, struct listd_node *s)
{
    struct listd_node t;

    if (unlikely(listd_empty(s)))
        return ;
    listd_init(&t);
    listd_cut(&t, n, s);
    listd_move_tail(d, &t);
    return ;
}

/**
 * 双链表结点遍历，遍历过程中不支持 listd_del(node)
 * @node 所遍历结点地址
 * @head 头结点地址
 */
#define listd_foreach(node, head)                                   \
    for (node=(head)->next; node!=(head); node=node->next)

/**
 * 双链表逆向遍历，遍历过程中不支持 listd_del(node)
 * @node 所遍历结点地址
 * @head 头结点地址
 */
#define listd_foreach_prev(node, head)                              \
    for (node=(head)->prev; node!=(head); node=node->prev)

/**
 * 双链表结点遍历，支持 listd_del(node)
 * @node 所遍历结点地址
 * @next @node 后向结点地址
 * @head 头结点地址
 */
#define listd_foreach_safe(node, nextn, head)                       \
    for (node =(head)->next;                                        \
         node!=(head) && ({nextn=node->next; 1;});                  \
         node=nextn)

/**
 * 双链表结点逆向遍历，支持 listd_del(node)
 * @node 所遍历结点地址
 * @prev @node 前向地点地址
 * @head 头结点地址
 */
#define listd_foreach_safe_prev(node, prevn, head)                  \
    for (node=(head)->prev;                                         \
         node!=(head) && ({prevn=node->prev; 1;});                  \
         node=prevn)

/**
 * 获取双向链表结点所属数据对象地址
 * @node  结点地址
 * @head  头结点地址
 * @chief 数据对象地址
 * @mbr   数据对象中串联双链表的结点命名
 */
#define listd_chief(node, head, chief, mbr) ({                      \
    (node)!=(head) ? startof(node, typeof(*chief), mbr) : NULL;     \
})

/**
 * 双向链表数据对象遍历，不支持 listd_chief_del(chief)
 * @chief 所遍历数据对象地址
 * @head  头结点地址
 * @mbr   数据对象中串联双链表的结点命名
 */
#define listd_foreach_chief(chief, head, mbr)                       \
    for (chief = listd_chief((head)->next,head,chief,mbr);          \
         chief;                                                     \
         chief = listd_chief(chief->mbr.next,head,chief,mbr))

/**
 * 双向链表数据对象逆向遍历，不支持 listd_chief_del(chief)
 * @chief 所遍历数据对象地址
 * @head  头结点地址
 * @mbr   数据对象中串联双链表的结点命名
 */
#define listd_foreach_chief_prev(chief, head, mbr)                  \
    for (chief = listd_chief((head)->prev,head,chief,mbr);          \
         chief;                                                     \
         chief = listd_chief(chief->mbr.prev,head,chief,mbr))

/**
 * 双向链表数据对象遍历，支持 listd_chief_del(chief)
 * @chief 所遍历数据对象地址
 * @next  @chief 后向数据对象地址
 * @head  头结点地址
 * @mbr   数据对象中串联双链表的结点命名
 */
#define listd_foreach_chief_safe(chief, nextn, head, mbr)           \
    for (chief = listd_chief((head)->next, head, chief, mbr);       \
         chief &&                                                   \
         ({nextn=listd_chief(chief->mbr.next,head,chief,mbr); 1;}); \
         chief = nextn)

/**
 * 双向链表数据对象逆向遍历，支持 listd_chief_del(chief)
 * @chief 所遍历数据对象地址
 * @prev  @chief 前向数据对象地址
 * @head  头结点地址
 * @mbr   数据对象中串联双链表的结点命名
 */
#define listd_foreach_chief_safe_prev(chief, prevn, head, mbr)      \
    for (chief = listd_chief((head)->prev, head, chief, mbr);       \
         chief &&                                                   \
         ({prevn=listd_chief(chief->mbr.prev,head,chief,mbr); 1;}); \
         chief = prevn)

#if 0
#endif
struct listh_node {
    struct listh_node  *next;
    struct listh_node **pprev;
};

struct listh_head {
    struct listh_node *next;
};

/**
 * 初始化哈希桶 @h 
 */
static inline void listh_head_init(struct listh_head *h)
{
    h->next = NULL;
    return ;
}

/**
 * 判断哈希桶 @h 是否为空
 */
static inline bool listh_empty(struct listh_head *h)
{
    return !h->next;
}

/**
 * 初始化哈希结点 @n
 */
static inline void listh_node_init(struct listh_node *n)
{
    n->next  = NULL;
    n->pprev = NULL;
    return ;
}

/**
 * 将结点 @n 加入到哈希桶 @h 之后
 */
static inline void 
listh_add_head(struct listh_node *n, struct listh_head *h)
{
    n->next  = h->next;
    n->pprev = &h->next;
    h->next  = n;
    return ;
}

/**
 * 将结点 @n 加在结点 @prev 之后
 */
static inline void listh_add_behind(struct listh_node *n, 
    struct listh_node *prev)
{
    struct listh_node *t;

    n->next  = prev->next;
    n->pprev = &prev->next;
    if ((t=n->next))
        t->pprev = &n->next;
    return ;
}

/**
 * 将结点 @n 加在结点 @next 之前
 */
static inline void listh_add_before(struct listh_node *n,
    struct listh_node *next)
{
    n->next = next;
    *next->pprev = n;
    n->pprev = next->pprev;
    next->pprev = &n->next;
    return ;
}

/**
 * 在相应哈希桶中将结点 @n 删除
 */
static inline void listh_del(struct listh_node *n)
{
    struct listh_node *t;

    if ((t=n->next))
        t->pprev = n->pprev;
    *n->pprev = n->next;
    return ;
}
/**
 * 从数据对象 @chief 所属哈希桶中删除该对象
 * @mbr 数据对象中串联哈希表的结点命名
 */
#define listh_chief_del(chief, mbr) listh_del(&(chief)->mbr)

/**
 * 哈希桶结点遍历
 * @node 所遍历结点地址
 * @head 哈希桶结点地址
 */
#define listh_foreach(node, head)                               \
    for (node=(head)->next; node; node=(node)->next)

/**
 * 哈希桶结点遍历，支持 listh_del(node)
 * @node 所遍历结点地址
 * @next @node 后向结点地址
 * @head 哈希桶结点地址
 */
#define listh_foreach_safe(node, nextn, head)                   \
    for (node=(head)->next;                                     \
         node && ({nextn=node->next; 1;});                      \
         node=nextn)

/**
 * 获取哈希表结点所属数据对象地址
 * @node  结点地址
 * @chief 数据对象地址
 * @mbr   数据对象中串联哈希表的结点命名
 */
#define listh_chief(node, chief, mbr) ({                        \
    (node) ? startof(node,typeof(*(chief)),mbr) : NULL;         \
})

/**
 * 哈希桶数据对象遍历
 * @chief 所遍历数据对象地址
 * @head  哈希桶首地址
 * @mbr   数据对象中串联哈希表的结点命名
 */
#define listh_foreach_chief(chief, head, mbr)                   \
    for (chief=listh_chief((head)->next,chief,mbr);             \
         chief;                                                 \
         chief=listh_chief(chief->mbr.next,chief,mbr))

/**
 * 哈希桶数据对象遍历，支持 listh_chief_del(chief)
 * @chief 所遍历数据对象地址
 * @next  @chief 后向数据对象地址
 * @head  哈希桶首地址
 * @mbr   数据对象中串联哈希表的结点命名
 */
#define listh_foreach_chief_safe(chief, nextn, head, mbr)       \
    for (chief = listh_chief((head)->next, chief, mbr);         \
         chief &&                                               \
         ({nextn=listh_chief(chief->mbr.next,chief,mbr); 1;});  \
         chief = nextn)

#endif